#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣2560. 打家劫舍 IV
// 【难度】中等
// 【提交】2025.9.25 https://leetcode.cn/problems/house-robber-iv/submissions/665997771/
// 【标签】二分查找；贪心算法；动态规划

//这段是抄的
const auto _ = std::cin.tie(nullptr)->sync_with_stdio(false);
#define LC_HACK
#ifdef LC_HACK
const auto __ = []() {
    struct ___ {
        static void _() { std::ofstream("display_runtime.txt") << 0 << '\n'; }
    };
    std::atexit(&___::_);
    return 0;
}();
#endif

class Solution_LC2560 {
public:
    int minCapability(vector<int>& nums, int k) {
        if (k == 0) return 0;
        
        auto check = [&](int mx) -> bool {
            int cnt = 0;
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] <= mx) {
                    cnt++;
                    i++;
                }
            }
            return cnt >= k;
        };
        
        int left = 0, right = *max_element(nums.begin(), nums.end());
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? right : left) = mid;
        }
        return right;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组nums表示每个房屋的价值，和一个整数k表示需要偷的房屋数量。
 * 要求选择k个不相邻的房屋，使得所选房屋的最大价值最小化。
 * 模型：二分查找+贪心验证，通过二分法确定可能的最小最大能力值。
 * 
 * 二、标准解法状态设计
 * 1. 使用二分查找确定可能的最小能力值，范围是[0, 数组中的最大值]。
 * 2. 对于每个候选的能力值mid，使用贪心算法验证是否能偷至少k个不相邻的房屋。
 * 3. 贪心策略是尽可能选择价值不超过mid的房屋，同时跳过相邻的房屋。
 * 
 * 三、你的实现思路
 * 使用二分查找法确定最小可能的能力值，对于每个候选值使用贪心算法进行验证。
 * 使用三元运算符简化了二分查找的赋值操作。
 * 
 * 四、逐行注释（带细节提醒）
 * if (k == 0) return 0; // 特殊情况处理
 * 
 * auto check = [&](int mx) -> bool { // 定义检查函数
 *     int cnt = 0; // 计数器
 *     for (int i = 0; i < nums.size(); i++) {
 *         if (nums[i] <= mx) { // 如果房屋价值不超过mx
 *             cnt++; // 增加偷取的房屋计数
 *             i++; // 跳过下一个房屋，避免偷相邻房屋
 *         }
 *     }
 *     return cnt >= k; // 返回是否能偷足够多的房屋
 * };
 * 
 * int left = 0, right = *max_element(nums.begin(), nums.end()); // 二分查找边界
 * while (left + 1 < right) { // 使用左闭右开的二分查找模板
 *     int mid = left + (right - left) / 2; // 计算中间值
 *     (check(mid) ? right : left) = mid; // 使用三元运算符简化赋值
 * }
 * return right; // 返回最小可行能力值
 * 
 * 五、正确性证明
 * 二分查找可以正确找到满足条件的最小能力值，因为如果某个值mx可行，那么所有更大的值也可行。
 * 贪心策略的正确性基于：为了最大化偷取的房屋数量，应该尽可能选择价值低的房屋，并且跳过相邻房屋。
 * 
 * 六、复杂度
 * 时间：O(n log M)，其中n是数组长度，M是数组中的最大值。
 *     二分查找需要O(log M)次迭代，每次验证需要O(n)。
 * 空间：O(1)，只使用了常数级别的额外空间。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法效率高，能够处理较大规模的数据；
 *   - 思路清晰，结合了二分查找和贪心算法的优点；
 *   - 代码实现简洁，使用三元运算符简化了赋值操作。
 * 缺点：
 *   - 贪心策略可能不是最直观的解法；
 *   - 三元运算符可能降低代码可读性；
 *   - 调试代码可能影响在线评测。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (nums.empty() || k > (nums.size() + 1) / 2) return -1;
 * 2. 使用更明确的变量名（如 capability 代替 mx）来增强可读性；
 * 3. 对于在线评测，可以移除调试代码；
 * 4. 可以考虑使用动态规划解法，虽然时间复杂度更高但更直观。
 * 
 * 九、一句话总结
 * 通过二分查找确定最小可能的能力值，并结合贪心算法进行验证，你的实现高效且准确，
 * 但需要注意调试代码可能影响在线评测环境。
 */